package madixin.t437;

class Solution {
    private int count = 0;

    public int pathSum(TreeNode root, int sum) {

        if (root == null) {
            return 0;
        }

        pathSumWithRoot(root, sum);
        pathSum(root.left, sum);
        pathSum(root.right, sum);

        return count;
    }

    private void pathSumWithRoot(TreeNode node, int sum) {
        if (node == null) {
            return;
        }

        if (node.val == sum) {
            count++;
            return;
        }
        pathSumWithRoot(node.left, sum - node.val);
        pathSumWithRoot(node.right, sum - node.val);

    }

}